Corso di Laurea in Informatica Linguaggio e Metodi della Matematica Prova scritta del 16 Gennaio 2003

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Numero di matricola: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Corso e Aula:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1. Sia A = {n ∈ ℕ | 1 ≤ n ≤ 3} e sia B = {n ∈ ℕ | 1 ≤ n ≤ 2}. Determinare le cardinalità di A × B e B × A, e stabilire se è possibile trovare una funzione f: A × B → B × A che sia:

1. iniettiva e surgettiva.

2. iniettiva ma non surgettiva.

3. surgettiva ma non iniettiva.

4. nè iniettiva nè surgettiva.

Si giustifichino le risposte e nei casi di risposta positiva si dia un esempio di funzione con le proprietà richieste.

Esercizio 2. Scriviamo x | y per indicare che l’intero x divide l’intero y. Si determini quali delle seguenti affermazioni è vera nel dominio degli interi.

\begin{matrix}1. ∃x ∀y x | y. & 2. ∀x ∃y x | y. & 3. ∀x ∀y x | y. & 4. ∃x ∃y x | y. \\ 5. ∀x ∀y (x | y → y | x). & 6. ∃x ∃y (x | y ∧ y | x). & 7. ∀x ∃y (x | y ∧ y | x). \end{matrix}

Esercizio 3. Una stringa binaria è una stringa formata dai simboli 0, 1. Tra tutte le stringhe binarie di lunghezza 7, si determini quante sono quelle:

1. dove occorrono esattamente due simboli 1.

2. dove occorrono esattamente due simboli 1, i quali non occupano posizioni consecutive.

3. che sono palindrome, ovvero sono identiche se lette da destra a sinistra o da sinistra a destra. (Ad esempio, la stringa 0110110 è una stringa palindroma di lunghezza 7.)

Esercizio 4. Si consideri la successione definita ponendo f_{1} = 1, f_{2} = 1, f_{n+2} = f_{n+1} + f_{n}. Dimostrare che 2f_{n} ≥ 3n + 4 per ogni n ≥ 7.

Esercizio 5.

1. Determinare l’insieme di tutti i numeri interi che divisi per 7 danno come resto 3 e divisi per 5 danno come resto 2. Si stabilisca quanti di questi numeri sono compresi nell’intervallo tra 0 e 1000.

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Numero di matricola: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Corso e Aula:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1. Sia A = {n ∈ ℕ | 1 ≤ n ≤ 2} e sia B = {n ∈ ℕ | 1 ≤ n ≤ 4}. Determinare le cardinalità di A × B e B × A, e stabilire se è possibile trovare una funzione f: A × B → B × A che sia:

1. iniettiva ma non surgettiva.

2. surgettiva ma non iniettiva.

3. nè iniettiva nè surgettiva.

4. iniettiva e surgettiva.

Si giustifichino le risposte e nei casi di risposta positiva si dia un esempio di funzione con le proprietà richieste.

Esercizio 2. Scriviamo x | y per indicare che l’intero x divide l’intero y. Si determini quali delle seguenti affermazioni è vera nel dominio degli interi.

\begin{matrix}1. ∀x ∃y x | y. & 2. ∃x ∃y x | y. & 3. ∃x ∀y x | y. & 4. ∀x ∀y x | y. \\ 5. ∀x ∀y (x | y ∨ y | x). & 6. ∀x ∀y (x | y ∧ y | x). & 7. ∃x ∀y (x | y ∧ y | x). \end{matrix}

Esercizio 3. Una stringa binaria è una stringa formata dai simboli 0, 1. Tra tutte le stringhe binarie di lunghezza 8, si determini quante sono quelle:

1. che sono palindrome, ovvero sono identiche se lette da destra a sinistra o da sinistra a destra. (Ad esempio, la stringa 01100110 è una stringa palindroma di lunghezza 8.)

2. dove occorrono almeno due simboli 0.

3. dove occorrono esattamente due simboli 1, i quali non occupano posizioni consecutive.

Esercizio 4. Si consideri la successione definita ponendo f_{1} = 1, f_{2} = 1, f_{n+2} = f_{n+1} + f_{n}. Dimostrare che 3f_{n} ≥ 4n + 2 per ogni n ≥ 7.

Esercizio 5.

1. Determinare l’insieme di tutti i numeri interi che divisi per 11 danno come resto 3 e divisi per 3 danno come resto 2. Si stabilisca quanti di questi numeri sono compresi nell’intervallo tra 0 e 800.

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Numero di matricola: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Corso e Aula:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1. Sia A = {n ∈ ℕ | 1 ≤ n ≤ 2} e sia B = {n ∈ ℕ | 1 ≤ n ≤ 5}. Determinare le cardinalità di A × B e B × A, e stabilire se è possibile trovare una funzione f: A × B → B × A che sia:

1. surgettiva ma non iniettiva.

2. nè iniettiva nè surgettiva.

3. iniettiva e surgettiva.

4. iniettiva ma non surgettiva.

Si giustifichino le risposte e nei casi di risposta positiva si dia un esempio di funzione con le proprietà richieste.

Esercizio 2. Scriviamo x | y per indicare che l’intero x divide l’intero y. Si determini quali delle seguenti affermazioni è vera nel dominio degli interi.

\begin{matrix}1. ∀x ∀y x | y. & 2. ∃x ∀y x | y. & 3. ∃x ∃y x | y. & 4. ∀x ∃y x | y. \\ 5. ∀x ∀y (x | y → y | x). & 6. ∀x ∃y (x | y ∧ y | x). & 7. ∃x ∃y (x | y ∧ y | x). \end{matrix}

Esercizio 3. Una stringa binaria è una stringa formata dai simboli 0, 1. Tra tutte le stringhe binarie di lunghezza 9, si determini quante sono quelle:

1. dove occorrono esattamente tre simboli 1.

2. che sono palindrome, ovvero sono identiche se lette da destra a sinistra o da sinistra a destra. (Ad esempio, la stringa 011010110 è una stringa palindroma di lunghezza 9.)

3. dove occorrono esattamente due simboli 1, i quali non occupano posizioni consecutive.

Esercizio 4. Si consideri la successione definita ponendo f_{1} = 1, f_{2} = 1, f_{n+2} = f_{n+1} + f_{n}. Dimostrare che 4f_{n} ≥ 6n + 3 per ogni n ≥ 7.

Esercizio 5.

1. Determinare l’insieme di tutti i numeri interi che divisi per 13 danno come resto 3 e divisi per 3 danno come resto 2. Si stabilisca quanti di questi numeri sono compresi nell’intervallo tra 0 e 900.

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Numero di matricola: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Corso e Aula:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1. Sia A = {n ∈ ℕ | 1 ≤ n ≤ 3} e sia B = {n ∈ ℕ | 1 ≤ n ≤ 4}. Determinare le cardinalità di A × B e B × A, e stabilire se è possibile trovare una funzione f: A × B → B × A che sia:

1. iniettiva ma non surgettiva.

2. surgettiva ma non iniettiva.

3. nè iniettiva nè surgettiva.

4. iniettiva e surgettiva.

Si giustifichino le risposte e nei casi di risposta positiva si dia un esempio di funzione con le proprietà richieste.

Esercizio 2. Scriviamo x | y per indicare che l’intero x divide l’intero y. Si determini quali delle seguenti affermazioni è vera nel dominio degli interi.

\begin{matrix}1. ∃x ∃y x | y. & 2. ∀x ∃y x | y. & 3. ∃x ∀y x | y. & 4. ∀x ∀y x | y. \\ 5. ∀x ∀y (x | y ∨ y | x). & 6. ∃x ∀y (x | y ∧ y | x). & 7. ∀x ∀y (x | y ∧ y | x). \end{matrix}

Esercizio 3. Una stringa binaria è una stringa formata dai simboli 0, 1. Tra tutte le stringhe binarie di lunghezza 10, si determini quante sono quelle:

1. dove occorrono almeno due simboli 0;

2. dove occorrono esattamente due simboli 0, i quali non occupano posizioni consecutive.

3. che sono palindrome, ovvero sono identiche se lette da destra a sinistra o da sinistra a destra. (Ad esempio, la stringa 0100110010 è una stringa palindroma di lunghezza 10.)

Esercizio 4. Si consideri la successione definita ponendo f_{1} = 1, f_{2} = 1, f_{n+2} = f_{n+1} + f_{n}. Dimostrare che 5f_{n} ≥ 7n − 3 per ogni n ≥ 6.

Esercizio 5.

1. Determinare l’insieme di tutti i numeri interi che divisi per 11 danno come resto 3 e divisi per 5 danno come resto 2. Si stabilisca quanti di questi numeri sono compresi nell’intervallo tra 0 e 700.